Techniques for transmission of files between a sender and a recipient over a communications channel are the subject of much literature. Preferably, a recipient desires to receive an exact copy of data transmitted over a channel by a sender with some level of certainty. Where the channel does not have perfect fidelity (which covers most all physically realizable systems), one concern is how to deal with data lost or garbled in transmission. Lost data (erasures) are often easier to deal with than corrupted data (errors) because the recipient cannot always tell when corrupted data is data received in error. Many error-correcting codes have been developed to correct for erasures and/or for errors. Typically, the particular code used is chosen based on some information about the infidelities of the channel through which the data is being transmitted and the nature of the data being transmitted. For example, where the channel is known to have long periods of infidelity, a burst error code might be best suited for that application. Where only short, infrequent errors are expected a simple parity code might be best.
As used herein, “source data” refers to data that is available at one or more senders and that a receiver is used to obtain, by recovery from a transmitted sequence with or without errors and/or erasures, etc. As used herein, “encoded data” refers to data that is conveyed and can be used to recover or obtain the source data. In a simple case, the encoded data is a copy of the source data, but if the received encoded data differs (due to errors and/or erasures) from the transmitted encoded data, in this simple case the source data might not be entirely recoverable absent additional data about the source data. Transmission can be through space or time. In a more complex case, the encoded data is generated based on source data in a transformation and is transmitted from one or more senders to receivers. The encoding is said to be “systematic” if the source data is found to be part of the encoded data. In a simple example of systematic encoding, redundant information about the source data is appended to the end of the source data to form the encoded data.
Also as used herein, “input data” refers to data that is present at an input of an FEC (forward-error correcting) encoder apparatus or an FEC encoder module, component, step, etc., (“FEC encoder”) and “output data” refers to data that is present at an output of an FEC encoder. Correspondingly, output data would be expected to be present at an input of an FEC decoder and the FEC decoder would be expected to output the input data, or a correspondence thereof, based on the output data it processed. In some cases, the input data is, or includes, the source data, and in some cases, the output data is, or includes, the encoded data. For example, the input data would be the source data if there is no processing before the input of an FEC encoder. However, in some cases, the source data is processed into a different form (e.g., a static encoder, an inverse encoder or another process) to generate intermediate data that is presented to the FEC encoder instead of the source data.
In some cases, a sender device or sender program code may comprise more than one FEC encoder, i.e., source data is transformed into encoded data in a series of a plurality of FEC encoders. Similarly at the receiver, there may be more than one FEC decoder applied to generate source data from received encoded data.
Data can be thought of as partitioned into symbols. An encoder is a computer system, device, electronic circuit, or the like, that generates encoded symbols or output symbols from a sequence of source symbols or input symbols and a decoder is the counterpart that recovers a sequence of source symbols or input symbols from received or recovered encoded symbols or output symbols. The encoder and decoder are separated in time and/or space by the channel and any received encoded symbols might not be exactly the same as corresponding transmitted encoded symbols and they might not be received in exactly the same sequence as they were transmitted. The “size” of a symbol can be measured in bits, whether or not the symbol is actually broken into a bit stream, where a symbol has a size of M bits when the symbol is selected from an alphabet of 2M symbols. In many of the examples herein, symbols are measured in octets and codes might be over a field of 256 possibilities (there are 256 possible 8-bit patterns within each octet), but it should be understood that different units of data measurement can be used and it is well-known to measure data in various ways. In the general literature, the term “byte” is sometimes used interchangeably with the term “octet” to indicate an 8-bit value, although in some contexts “byte” indicates an X-bit value where X is not equal to 8, e.g., X=7, and thus, in general, the term “octet” is used herein. Unless otherwise indicated, the examples herein are not limited to a particular integer or non-integer number of bits per symbol.
FIG. 1 shows the general work flow associated with coding and decoding and the terminology used to describe the block structure of a source block, symbols, sub-blocks, etc. Symbols may be either source symbols (i.e., copies of the blocks constituting the original object) or repair symbols (i.e., data produced by the coding process that can be used to repair erasures in the source blocks). Parameters critical to the operation of the coding system might be contained within a structure called the Object Transmission Information (“OTI”). The OTI for a collection of related symbols may be communicated one or more times between sender(s) and receiver(s). When symbols are placed into messages for delivery via a channel (e.g., a network packet over a network), bookkeeping information is sometimes added to the symbols. This information is placed within the Payload Identifier (FEC Payload ID). In several particular examples, the Payload ID contains a source block number (“SBN”) and a unique encoding symbol identifier (“ESI”). The Payload ID (and OTI) can contain different information for different types of codes and use cases.
Forward Error Correction (“FEC”) Object Transmission Information (“OTI”), or “FEC OTI”
Based on the FEC OTI a receiver receives (or is able to infer), the receiver can determine the source block and sub-block structure of the file transfer. In [Raptor-RFC-5053] and [IETF-RFC-6330], the FEC Payload ID contains the pair (SBN, ESI), where in [Raptor-RFC-5053] SBN is 16 bits and the ESI is 16 bits, whereas in [IETF-RFC-6330] the SBN is 8 bits and the ESI is 24 bits, as illustrated in FIG. 2 herein. One disadvantage of this format is that one has to pre-determine the number of bits to allocate to the SBN and to the ESI, and it is sometimes difficult to determine a proper mix that will be adequate for all file delivery parameters.
For example, when using [Raptor-RFC-5053] with 16-bit ESIs, having only 216=65,536 ESI values available might be limiting in some situations. For example, with a source block containing 8,192 source symbols, the number of encoded symbols can only be a factor of 8 larger (i.e., because 8192*8=65536), limiting the possible code rate that could be used to below ⅛ in this case. In this example, using 16 bits to hold the SBN (providing for up to 216=65,536 source blocks) could be more than would ever be used. More concretely, with 8,192 source symbols of 1,024 octets each, the size of the file that could be supported is 524 GB, which in many applications is orders of magnitude larger than is needed.
As another example, when using [IETF-RFC-6330], having only 28=256 SBNs available might be limiting in some situations. For a 4 GB file, if each source block is limited to 8 MB (which might be the case if the maximum sub-block size is 256 KB, the minimum sub-symbol size is 32 octets, and the symbol size is 1,024 octets) then limiting the number of source blocks to 256 limits the file size to 2 GB. In this example, it may be that having 224=16,777,216 possible encoded symbols (ESIs) are more than would ever be used, e.g., with 8,192 source symbols the number of possible encoded symbols is 2,048 times larger, which may never be needed in some applications.
Erasure code processing as described above can be used in conjunction with a variety of content delivery systems and protocols. In some cases, specialized servers are required, which can be more expensive to implement, support and maintain that using more common, conventional Internet servers to support content delivery. Therefore, it is desirable to have methods for delivering content and repair symbols that are less complex to implement.
In some cases, it is preferable to use more efficient signaling methods. One such method, designed for use with uni-directional communication channels and multicast communication is known as FLUTE [FLUTE]. FLUTE augments the basic capabilities of the erasure coding techniques with methods to deliver file and directory information (e.g., file names to be associated with streams of symbols). A receiver that implements both FLUTE and the appropriate set of erasure codes is able to identify the names and contents of file objects. FLUTE can, in turn, be carried within (or on “top” of) a variety of transfer mechanisms such as UDP/IP (e.g., in the Internet). In the context of MBMS and eMBMS, where the 3GPP standards defining organization sets standards, FLUTE has been selected for delivery of streaming content. In particular, the stream is delivered as a sequence of DASH formatted files. However, the signaling within FLUTE is not specifically designed for delivering sequence of related files. Thus, improved methods for signaling and delivering sequences of files within the FLUTE architecture is needed.